package leetcode.lt100;

public class Solution_86 {

    public static void main(String[] args) {
        ListNode head = new ListNode(2);
        head.append(5).append(6).append(7).append(1).append(1);
        System.out.println(partition(head, 3));
    }

    public static ListNode partition(ListNode head, int x) {
        ListNode cur = head;
        ListNode last = null;
        ListNode large = null;
        ListNode largeNode = null;
        while (cur != null) {
            if (cur.val >= x) {
                if (large == null) {
                    large = new ListNode(cur.val);
                    largeNode = large;
                } else {
                    largeNode.next = new ListNode(cur.val);
                    largeNode = largeNode.next;
                }
                if (last != null) {
                    last.next = cur.next;
                } else {
                    head = cur.next;
                }
            } else {
                last = cur;
            }
            cur = cur.next;
        }
        if (last == null) {
            return large;
        } else {
            last.next = large;
            return head;
        }
    }
}